import java.util.Arrays;

/**
 * @Author MRC
 * @Description 几种排序的演示
 * @Date 9:52 2020/5/25
 **/
public class Sort1 {


    public static void main(String[] args) {

        int[] arrays = {3, 4, 2, 1, 5, 6, 7, 8};

        int[] num = {49, 38, 65, 97, 76, 13, 27, 49};

        sort5(num);
    }

    /**
     * @return void
     * @Author MRC
     * @Description 冒泡排序第一版
     * @Date 22:00 2020/4/22
     * @Param []
     **/
    public static void sort1(int[] arrays) {

        int allChange = 0;
        for (int i = 0; i < arrays.length; i++) {

            for (int j = 0; j < arrays.length - i - 1; j++) {

                if (arrays[j] > arrays[j + 1]) {

                    int temp = arrays[j];
                    arrays[j] = arrays[j + 1];
                    arrays[j + 1] = temp;
                }
                allChange++;
            }
            System.out.println(Arrays.toString(arrays));
        }

        System.out.println("总比较次数：" + allChange);
    }

    /**
     * @return void
     * @Author MRC
     * @Description 冒泡排序第二版
     * @Date 21:48 2020/4/22
     * @Param [arrays]
     **/
    public static void sort2(int[] arrays) {

        int allChange = 0;

        for (int i = 0; i < arrays.length; i++) {

            boolean isChange = true;

            for (int j = 0; j < arrays.length - i - 1; j++) {

                if (arrays[j] > arrays[j + 1]) {

                    int temp = arrays[j];
                    arrays[j] = arrays[j + 1];
                    arrays[j + 1] = temp;

                    isChange = false;
                }
                allChange++;
            }
            System.out.println(Arrays.toString(arrays));
            if (isChange) {
                break;
            }
        }
        System.out.println("总比较次数：" + allChange);
    }

    /**
     * @return void
     * @Author MRC
     * @Description 冒泡排序第三版
     * @Date 21:39 2020/4/22
     * @Param [array]
     **/
    public static void sort3(int[] array) {

        //用来记录最后一次发生变化的位置
        int lastChangeIndex = 0;
        //用来表示需要比较的长度。只需要比较到之前即可
        int sortLength = array.length - 1;

        int allChange = 0;

        for (int i = 0; i < array.length; i++) {

            boolean isChange = true;

            for (int j = 0; j < sortLength; j++) {

                if (array[j] > array[j + 1]) {

                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;

                    isChange = false;
                    //记录发生变化的位置
                    lastChangeIndex = j;
                }
                //用于记录比较次数
                allChange++;
            }
            sortLength = lastChangeIndex;
            System.out.println(Arrays.toString(array));
            //若无改变则跳出循环
            if (isChange) {
                break;
            }
        }
        System.out.println("总比较次数：" + allChange);
    }


    /**
     * @return void
     * @Author MRC
     * @Description 冒泡排序第四版 鸡尾酒排序
     * @Date 22:25 2020/4/23
     * @Param [array]
     **/
    public static void sort4(int[] array) {

        int temp = 0;
        int allChange = 0;

        int lastRightIndex = 0;
        int lastLeftIndex = 0;

        /**
         * 外层循环用于控制程序总体循环次数
         */
        for (int i = 0; i < array.length / 2; i++) {

            /**
             * 有无交换元素标记
             */
            boolean isChange = true;

            //从左向右摆动
            for (int j = i; j < array.length - i - 1; j++) {

                if (array[j] > array[j + 1]) {

                    //交换元素
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;

                    isChange = false;
                }
                allChange++;
            }

            if (isChange) break;

            isChange = true;
            //从右向左摆动
            for (int g = array.length - i - 1; g > i; g--) {

                if (array[g] < array[g - 1]) {

                    temp = array[g];

                    array[g] = array[g - 1];
                    array[g - 1] = temp;

                    isChange = false;
                }
                allChange++;
            }
            if (isChange) break;
        }
        System.out.println(Arrays.toString(array));
        System.out.println("总体比较次数：" + allChange);
    }

    public static void sort5(int[] array) {


        int temp = 0;
        int allChange = 0;

        //记录左边界
        int leftBorder = 0;
        //右边界
        int rightBorder = array.length - 1;
        //左边发生变化的位置
        int leftChangeIndex = 0;
        //右边发生变化的位置
        int rightChangeIndex = 0;

        /**
         * 外层循环用于控制程序总体循环次数
         */
        for (int i = 0; i < array.length / 2; i++) {

            /**
             * 有无交换元素标记
             */
            boolean isChange = true;

            //从左向右摆动
            for (int j = leftBorder; j < rightBorder; j++) {

                if (array[j] > array[j + 1]) {

                    //交换元素
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;

                    isChange = false;

                    //记录右边边界
                    rightChangeIndex = j;
                }
                allChange++;
            }
            //用于下次循环终止
            rightBorder = rightChangeIndex;

            if (isChange) break;

            isChange = true;
            //从右向左摆动
            for (int g = rightBorder; g > leftBorder; g--) {

                if (array[g] < array[g - 1]) {

                    temp = array[g];

                    array[g] = array[g - 1];
                    array[g - 1] = temp;

                    isChange = false;
                    //记录左边界
                    leftChangeIndex = g;

                }
                allChange++;
            }
            leftBorder = leftChangeIndex;

            if (isChange) break;
        }
        System.out.println(Arrays.toString(array));
        System.out.println("总体比较次数：" + allChange);
    }

}
